package algorithm.EditStrMinCost;

/*
给定两个字符串s1和s2，问s2最少要删除多少个字符就可以变成s1的字串
 */
public class DeleteSubstrCost {
    public static final int BIGNUM = 10000;

    public static int getCost(String str1, String str2) {
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        int res = BIGNUM;

        for (int start = 0; start < s2.length; start++) {  //s2子串从i开始, 0表示str2[0]
            int[][] dp = new int[s1.length + 1][s2.length + 1 - start];  //dp中的1表示第1个字符
            for (int i = 1; i < s1.length + 1; i++) {
                dp[i][0] = i;
            }
            for (int i = 1; i < s2.length + 1 - start; i++) {
                dp[0][i] = BIGNUM;
            }
            for (int end = start; end < s2.length; end++) {  //从end结束
                res = Math.min(res, process(s1, s2, start, end, dp, BIGNUM, 1, BIGNUM));
            }
        }

        if (res > s1.length)
            res = -1;
        return res;
    }

    public static int process(char[] str1, char[] str2, int start, int end, int[][] dp, int ic, int dc, int rc) {
        for (int i = 1; i < str1.length + 1; i++) {
//            for (int j = start+1 - start; j <= end+1 - start; j++) {
//                if (str1[i-1] == str2[j-1 + start]) {
//                    dp[i][j] = dp[i-1][j-1];    //copy
//                } else {
//                    dp[i][j] = dp[i-1][j-1] + rc;   //replace
//                }
//                dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + dc);    //delete
//                dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + ic);    //insert
//            }

            int j = end + 1 - start;        //将复杂度从 O(N^3 * M) 降至 O(N^2 * M)
            if (str1[i-1] == str2[j-1 + start]) {
                    dp[i][j] = dp[i-1][j-1];    //copy
            } else {
                dp[i][j] = dp[i-1][j-1] + rc;   //replace
            }
            dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + dc);    //delete
            dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + ic);    //insert
        }
        return dp[str1.length][end+1 - start];
    }

    public static void main(String[] args) {
        String str1 = "xaxbxcx";
        String str2 = "a1bc1abc1";
        System.out.println(getCost(str1, str2));
    }
}
